package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/maximum-score-of-a-good-subarray/'>好子数组的最大分数(Maximum Score of a Good Subarray)</a>
 * <p>给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。</p>
 * <p>一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好子数组的两个端点下标需要满足 i <= k <= j 。</p>
 * <p>请你返回 好 子数组的最大可能 分数 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,4,3,7,4,5], k = 3
 *      输出：15
 *      解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。
 *
 * 示例 2：
 *      输入：nums = [5,5,4,5,4,1,1,1], k = 0
 *      输出：20
 *      解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= nums.length <= 10^5</li>
 *         <li>1 <= nums[i] <= 2 * 10^4</li>
 *         <li>0 <= k < nums.length</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/19 11:04
 */
public class LC1793MaximumScoreOfGoodSubarray_H {
    static class Solution {
        public int maximumScore(int[] nums, int k) {
            // 获取k位置的值，nums[k]。以该值为起始值，不断作-1操作，知道能包含数组中所有的值。
            int left = k - 1;
            int right = k + 1;
            int ans = 0;
            for (int currMinVal = nums[k]; ; ) {
                while (left >= 0 && nums[left] >= currMinVal) {
                    --left;
                }
                while (right < nums.length && nums[right] >= currMinVal) {
                    ++right;
                }
                ans = Math.max(ans, (right - left - 1) * currMinVal);
                // 如果一端越界。则以另一端的值为下一次的 currMinVal；
                // 如果两端都不越界。则以两端的值的最大值为下一次的 currMinVal；
                // 因为本次的currMinVal 和 下一次 currMinVal 中间的其他值，不会扩展left或right。currMinVal 减小只会是结果变小
                currMinVal = Math.max((left == -1 ? -1 : nums[left]), (right == nums.length ? -1 : nums[right]));
                // 如果两端都越界。说明数组中所有的数都大于 currMinVal 。
                // 此时 tempAns = currMinVal * n(数组长度,为固定值)
                // 再减小currMinVal计算出来的结果一定小于tempAns。所以直接退出
                if (currMinVal == -1) {
                    break;
                }
            }
            return ans;
        }
    }
}
